public class Solution {
    /**
     * 191. 位1的个数
     * https://leetcode.cn/problems/number-of-1-bits/description/
     * @param n
     * @return
     */
    public int hammingWeight(int n) {
        int ret = 0;
        for(int i = 0; i < 32; i++) {
            if(((n >> i) & 1) == 1) {
                ret++;
            }
        }
        return ret;
    }

    /**
     * 338. 比特位计数
     * https://leetcode.cn/problems/counting-bits/description/
     */
    //暴力穷举
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        ans[0] = 0;
        for(int i = 1; i < ans.length; i++) {
            int ret = 0;
            for(int j = 0; j < 32; j++) {
                if(((i >> j) & 1) == 1) ret++;
            }
            ans[i] = ret;
        }
        return ans;
    }
    //计算除去最右边1后的1的个数+1
    public int[] countBits1(int n) {
        int[] ans = new int[n + 1];
        ans[0] = 0;
        for(int i = 1; i < n + 1; i++) {
            ans[i] = ans[i & (i - 1)] + 1;
        }
        return ans;
    }

    /**
     * 461. 汉明距离
     * https://leetcode.cn/problems/hamming-distance/description/
     */
    //暴力穷举
    public int hammingDistance1(int x, int y) {
        int z = x ^ y;
        int ret = 0;
        for(int i = 0; i < 32; i++) {
            if(((z >> i) & 1) == 1) ret++;
        }
        return ret;
    }
    //两数异或后每次消一个1计数方法
    public int hammingDistance(int x, int y) {
        int ret = 0;
        for(int z = x ^ y; z > 0; z = z & (z - 1)) {
            ret++;
        }
        return ret;
    }
}